#define DataType int 
#define CAPCITY_INIT 2
#define CAPCITY_MULTIPLY 2
typedef struct stack
{
	DataType* data;
	int capcity;
	int size;
}stack;

void StInit(stack*);
void StDestory(stack*);

bool StCheck(stack*);
void StEnlarge(stack*);

void StPush(stack*, DataType);
void StPop(stack*);

DataType StTop(stack*);

bool STEmpty(stack*);

void StPrint(stack*);
void StInit(stack* s)
{
	s->data = (DataType*)malloc(sizeof(DataType) * CAPCITY_MULTIPLY);
	if (s->data == NULL)
	{
		perror("malloc");
		return;
	}
	s->capcity = CAPCITY_INIT;
	s->size = 0;
}

void StDestory(stack* s)
{
	free(s->data);
	s->data = NULL;
	s->capcity = 0;
	s->size = 0;
}

bool StCheck(stack* s)
{
	return s->capcity == s->size;
}

void StEnlarge(stack* s)
{
	DataType* tmp = (DataType*)realloc(s->data, sizeof(DataType) * s->capcity * CAPCITY_MULTIPLY);
	if (tmp == NULL)
	{
		perror("realloc");
		return;
	}
	s->data = tmp;
	s->capcity *= CAPCITY_MULTIPLY;
}
void StPush(stack* s, DataType x)
{
	if (StCheck(s))
		StEnlarge(s);
	s->data[s->size++] = x;
}
void StPop(stack* s)
{
	assert(!STEmpty(s));
	s->size--;
}

DataType StTop(stack* s)
{
	assert(s);
	assert(!STEmpty(s));
	return s->data[s->size - 1];
}

bool STEmpty(stack* s)
{
	assert(s);
	return !s->size;
}

typedef struct
{
	stack spush;
	stack spop;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
	StInit(&q->spush);
	StInit(&q->spop);
	return q;
}

void myQueuePush(MyQueue* obj, int x) {
	StPush(&obj->spush, x);
}

int myQueuePop(MyQueue* obj) {
	if (STEmpty(&obj->spop))
	{
		while (!STEmpty(&obj->spush))
		{
			DataType tmp = StTop(&obj->spush);
			StPop(&obj->spush);
			StPush(&obj->spop, tmp);
		}
	}
	DataType ret = StTop(&obj->spop);
	StPop(&obj->spop);
	return ret;
}

int myQueuePeek(MyQueue* obj) {
	if (STEmpty(&obj->spop))
	{
		while (!STEmpty(&obj->spush))
		{
			DataType tmp = StTop(&obj->spush);
			StPop(&obj->spush);
			StPush(&obj->spop, tmp);
		}
	}
	return StTop(&obj->spop);
}

bool myQueueEmpty(MyQueue* obj) {
	return STEmpty(&obj->spop) && STEmpty(&obj->spush);
}

void myQueueFree(MyQueue* obj) {
	StDestory(&obj->spush);
	StDestory(&obj->spop);
	free(obj);
	obj = NULL;
}